package yz.com.javautil.path;

import java.util.Stack;

/**
 * A*Algorithm
 *
 * @author Administrator
 */
public class TestFindPath {

    private static final int WID = 8;
    private static final int HEI = 8;
    private Stack stack = new Stack();

    public static void main(String[] args) {
        byte[] map = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        for (int i = 0; i < map.length; i++) {
            System.out.print(map[i] + " ");
            if (i % WID == WID - 1) {
                System.out.print("\n");
            }
        }
        System.out.print("\n");
        TestFindPath ai = new TestFindPath();
        ai.find(map, 12, 50);
    }

    public void find(byte[] map, int origin, int target) {
        int[] step = new int[2];
        step[1] = origin;
        stack.addElement(step);
        if (findPath(map, origin, target)) {
            System.out.println("success!");
            for (int i = 0; i < stack.size(); i++) {
                int[] temp = (int[]) stack.elementAt(i);
                System.out.println(i + " \t" + (char) temp[0] + " " + temp[1]);
            }
        } else {
            System.out.println("fail!");
        }
    }

    /**
     * 在地图上找到从原点到目标位置的路径
     *
     * @param map    地图数据
     * @param origin 开始位置
     * @param target 目标位置
     * @return 路径
     */
    private boolean findPath(byte[] map, int origin, int target) {
        char directL = 'l';
        char directR = 'r';
        char directU = 'u';
        char directD = 'd';
        if (canMoveTo(map, origin, target, directL)) {
            return true;
        }
        if (canMoveTo(map, origin, target, directR)) {
            return true;
        }
        if (canMoveTo(map, origin, target, directU)) {
            return true;
        }
        if (canMoveTo(map, origin, target, directD)) {
            return true;
        }
        // 如果四个方向都试过，全部不行，那么把当前步骤弹出
        stack.pop();
        return false;
    }

    /**
     * 是否可以向指定方向移动
     */
    private boolean canMoveTo(byte[] map, int origin, int target, char direct) {
        int next = 0;
        switch (direct) {
            case 'l':
                next = origin - 1;
                break;
            case 'r':
                next = origin + 1;
                break;
            case 'u':
                next = origin - WID;
                break;
            case 'd':
                next = origin + WID;
                break;
            default:
                break;
        }
        if (map[next] == 0) {
            // 如果目标位置可以进入
            if (next == target) {
                int[] step = new int[2];
                step[0] = direct;
                // 移动方向
                step[1] = next;
                // 到达的新位置
                stack.addElement(step);
                return true;
            }
            if (!inStack(next)) {
                int[] step = new int[2];
                step[0] = direct;
                step[1] = next;
                stack.addElement(step);
                if (findPath(map, next, target)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 检查这个位置是否在栈中已经存在了。为了防止在地图中转圈
     */
    private boolean inStack(int position) {
        int[] temp;
        for (int i = stack.size() - 1; i >= 0; i--) {
            temp = (int[]) stack.elementAt(i);
            if (position == temp[1]) {
                return true;
            }
        }
        return false;
    }
}



